package leetcode.code0023;

import java.util.PriorityQueue;

import leetcode.helper.tree.ListNode;

public class Solution extends Solution23 {

	@Override
	public ListNode mergeKLists(ListNode[] lists) {
		if (lists.length == 0)
			return null;
		PriorityQueue<Object[]> pq = new PriorityQueue<>((o1, o2) -> {
			return (int) o1[0] - (int) o2[0];
		});
		for (int i = 0; i < lists.length; i++) {
			ListNode ln = lists[i];
			if (ln != null)//不讲武德的判断
				pq.add(new Object[] { ln.val, i, ln });
		}
		ListNode head = new ListNode();
		ListNode p = head;
		while (!pq.isEmpty()) {
			Object[] top = pq.poll();
			p.next = new ListNode((int) top[0]);
			p = p.next;
			ListNode cur = (ListNode) top[2];
			if (cur.next != null) {
				cur = cur.next;
				pq.add(new Object[] { cur.val, top[1], cur });
			}
		}
		return head.next;
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
	}

}
